{ INFORMATICS.MCCME.RU
  Problem statement: http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=752
  Verdict: Accepted
}
uses SysUtils;
 
const 
	bad:int64=-round(1e12);
 
var
	i,n,l,r,q,qq,k,ans:longint;
	a:array[0..800010] of int64;
	b:array[0..200000] of int64;
 
function max(x,y:longint):longint;
begin
if b[x]>b[y] then result:=x else result:=y;
end;
 
function build(n:longint):longint; // returns number of elements in big array + builds array																	 
var                                // B - input data; A - RMQ array
	k,kk,i,j:longint;
 
begin
k:=1;
while k<=n do k:=k shl 1;
kk:=k;
k:=k shl 1;
b[0]:=bad;
for i:=n+1 to kk do 
	b[i]:=bad;
j:=1;
for i:=kk to k do begin
	a[i]:=j;
	inc(j);
end;
for i:=kk-1 downto 1 do
	a[i]:=max(a[i*2],a[i*2+1]);
result:=k;
end;
 
function rmq(l,r:longint):longint; // A - RMQ array; K - number of elements in A
var
	kk:longint;
begin
kk:=k shr 1;
inc(l,kk-1);
inc(r,kk-1);
result:=max(a[l],a[r]);
while r-l>1 do begin 
	if l mod 2=0 then result:=max(result,a[l+1]);
	if r mod 2=1 then result:=max(result,a[r-1]);
	l:=l div 2;
	r:=r div 2;	
end;
end;
 
begin
reset(input,'input.txt');
rewrite(output,'output.txt');
read(n);
for i:=1 to n do
	read(b[i]);
k:=build(n);
read(q);
for qq:=1 to q do begin
	read(l,r);
	ans:=rmq(l,r);
	writeln(b[ans],' ',ans);
end;
end.